1. Field of the Invention
The present invention relates to an error-correcting encoder, an error-correcting decoder and a data transmitting system with error-correcting codes.
2. Description of the Prior Art
Upon transmitting digital information, an error-correcting code is often used; one of the typical error-correcting codes is Reed-Solomon (RS) code. For further reference, the coding theory and RS code is disclosed in "Coding Theory", Hideki Imai, Electronic Information and Communication Meeting, 4th edition, Jun. 1, 1992.
The principle of the coding theory will be briefly explained below. To encode q-element RS code having a code length n and k information symbols, a polynomial having k information symbols, m.sub.k-1, . . . , m.sub.1, m.sub.0 as its coefficients: EQU M (x)=m.sub.k-1 x.sup.k-1 + . . . +m.sub.1 x+m.sub.0
is multiplied by x.sup.n-k, and the result of that is divided by a generating polynomial G (x) and the remainder is obtained. Namely, EQU R (x)=r.sub.n-k-1 x.sup.n-k-1 + . . . +r.sub.1 x+r.sub.0
that satisfies EQU M (x) x.sup.n-k =Q (x) G (x)+R (x)
is obtained. R (x) is called the remainder polynomial. And code polynomial W (x) is obtained by: EQU W (x)=M (x) x.sup.n-k -R (x)
The coefficients of W (x) are lined up from the term of the higher degree as follows: EQU (m.sub.k-1, . . . , m.sub.1, m.sub.0, -r.sub.n-k-1, -r.sub.1, -r.sub.0)
There appear k information symbols in the left-hand side of the above line and (n-k) check symbols appear in the right-hand side, which are obtained by multiplying coefficients of the remainder polynomial by (-1).
A conventional error-correcting encoder is now described referring to FIG. 11. In this case, a double-error-correcting RS code on the GF (Galois field) (2.sup.8), having code length n=255, number of information symbols k=251 and the minimum distance d=5, is used as the error-correcting code.
FIG. 11 is a block diagram showing the conventional error-correcting encoder. In FIG. 11, 501.sub.a -501.sub.d are Galois field multipliers which multiply each of the coefficients of the generating polynomial: EQU G (x)=x.sup.4 +g.sub.3 x.sup.3 +g.sub.2 x.sup.2 +g.sub.1 x+g.sub.0
The four Galois field multipliers perform the following multiplications respectively:
501.sub.a . . . .times.g.sub.3 PA1 501.sub.b . . . .times.g.sub.2 PA1 501.sub.c . . . .times.g.sub.1 PA1 501.sub.d . . . .times.g.sub.0 PA1 809 . . . .times..alpha..sup.-1 PA1 810 . . . .times..alpha..sup.-2
502.sub.a -502.sub.d denote 8-bit shift registers. E.sub.X OR gates 503.sub.a -503.sub.d perform E.sub.X OR operations bit by bit. 504.sub.a, 504.sub.b denote switches, 505 denotes an input terminal, and 506 denotes an output terminal.
The following describes the operation of the error-correcting encoder. The switch 504.sub.a is connected and the switch 504.sub.b is turned to the lower side of the circuit as shown in the FIG. 11. 251 information symbols, m.sub.250 -m.sub.0, are input with shifting one by one at the input terminal 505 sequentially. After all the information symbols are input, the switch 504.sub.a is disconnected, the switch 504.sub.b is turned to the opposite side of the circuit (the upper side of the circuit in FIG. 11) and the contents of the registers 502.sub.a -502.sub.d are output. In this way, the output terminal 506 transmits the coefficients of the code polynomial W (x) sequentially from the term of the higher degree.
A syndrome generator of a conventional error-correcting decoder is now described referring to FIG. 12. In this case, the syndrome generator receives the RS codes transmitted by the above-mentioned conventional error-correcting encoder.
Substituting root .alpha..sup.i (i=0, 1, 2, 3) (.alpha. is a root of a primitive polynomial) of generating polynomial G (x) to received polynomial EQU y (x)=y.sub.254 x.sup.254 + . . . +y.sub.1 x+y.sub.0
and syndrome S.sub.i =y (.alpha..sup.i) is obtained.
FIG. 12 is a block diagram showing the conventional syndrome generator. 601 denotes an 8-bit shift register. A Galois field multiplier 602 multiplies .alpha..sub.i. An E.sub.X OR gate 603 performs an E.sub.X OR operation bit by bit. 604 denotes an input terminal and 605 denotes an output terminal.
The operation of the syndrome generator will be explained below. The syndrome S.sub.i is calculated by inputting the coefficients of the received polynomials from y.sub.254 to y.sub.0, from higher to lower degree, sequentially at the input terminal 604, with shifting word by word. After all the received words are input, the syndrome S.sub.i is output from the output terminal 605.
A conventional Chien-Search circuit of the error-correcting decoder is now described referring to FIG. 13.
Chien-Search is a method for analyzing an error location by checking whether .delta. (.alpha..sup.i) is 0 or not with substituting .alpha..sup.i (i=0, 1, . . . , n-1), which shows the power of .alpha., to error location polynomial of t times error-correcting code: EQU .delta. (z)=z.sup.t +.delta..sub.t-1 z.sup.t-1 + . . . +.delta..sub.1 z+.delta..sub.0
When .delta. (.alpha..sup.i)=0, an error occurs at the received word y.sub.i of the received polynomial: EQU y (x)=y.sub.254 x.sup.254 + . . . +y.sub.1 x+y.sub.0
In this case, the codes transmitted by the above conventional encoder are received. The check symbol is double-error-correcting code and the error location polynomial .delta. (z) becomes: EQU .delta. (z)=z.sup.2 +.delta..sub.1 z+.delta..sub.0.
Coefficients .delta..sub.1, .delta..sub.0 of .delta. (z) are calculated previously from the syndrome. Detailed calculation of .delta..sub.1, .delta..sub.0 is described in the above-mentioned "Coding Theory", Hideki Imai, Electronic Information and communication meeting.
FIG. 13 is a block diagram showing the conventional Chien-Search circuit. In the figure, Galois field multipliers 701 and 702 perform the following multiplications respectively: EQU 701 . . . .times..alpha. EQU 702 . . . .times..alpha..sup.2
703.sub.a and 703.sub.b denote 8-bit shift registers. An E.sub.X OR gate 704 performs an E.sub.X OR operation bit by bit. 705 denotes an output terminal.
The following describes the operation of the Chien-Search circuit. Initial values .delta..sub.1 and "1" are set in the registers 703.sub.a and 703.sub.b, respectively. With shifting the received words, it is checked whether the sum of the outputs of the registers, that is, the output from the output terminal 705, becomes .delta..sub.0 or not. When the output becomes .delta..sub.0 at the initial status, .alpha..sup.0 is the root of .delta. (z), which means an error occurs in the received word y.sub.0. In the same way, when the output becomes .delta..sub.0 after i shifts, .alpha..sup.i is the root of .delta. (z) , which means an error occurs in the received word y.sub.i.
Another conventional error-correcting decoder is explained below referring to FIG. 14. In this case, the decoder receives shortened code on the GF (2.sup.8), in which the code length n is less than 255; for example, double-error-correcting RS code having the code length n=36, the number of information symbols k=32, and the minimum distance d=5. The error-correcting decoder generates a syndrome and detects the roots of the error location polynomial .delta. (z) by checking the terms from the highest degree by a Chien-Search.
In FIG. 14, a syndrome generating circuit 801 includes 4 syndrome generators, each of which was described above and shown in FIG. 12. Syndrome generator 804 generates syndrome S.sub.0, syndrome generator 805 generates syndrome S.sub.1, syndrome generator 806 generates syndrome S.sub.2, and syndrome generator 807 generates syndrome S.sub.3.
An error-location polynomial generator 802 calculates coefficients .delta..sub.0, .delta..sub.1 of the above error-location polynomial using the syndromes S.sub.0 -S.sub.3. A Chien-Search circuit 803, which is configured as shown in FIG. 13, sets the registers to the above values .delta..sub.0, .delta..sub.1 and analyzes the error-location. 812 denotes input terminals. 813 denotes an output terminal.
The operation of the decoder is explained below. The syndrome generating circuit 801 generates 4 syndromes S.sub.0, S.sub.1, S.sub.2, S.sub.3.
Using these syndromes, the error-location polynomial generator 802 calculates the coefficients .delta..sub.1, .delta..sub.0 of the error-location polynomial: EQU .delta. (z)=z.sup.2 +.delta..sub.1 z+.delta..sub.0
Then, Chien-Search circuit 803 performs a Chien-Search. Galois Field multipliers 809, 810 perform the following multiplications respectively:
.delta..sub.1 is set as an initial value in a register 808.sub.a and "1" is set in a register 808.sub.b. It is checked whether the sum of the outputs of the two registers, that is, the output from the output terminal 813, becomes .delta..sub.0 or not. Generally, a Chien-Search should be performed from the term of the highest degree in the received polynomial. In this example, the shortened code is received, in which the code length n=36, and the received polynomial becomes: EQU y (x)=y.sub.35 x.sup.35 + . . . +y.sub.1 x+y.sub.0
Thus, all the coefficients of the terms from 254 degrees to 36 degrees in the received polynomial become "0". Accordingly, it is required to shift the received word previously 255-36=219 times for searching an error-location from the term of 35 degrees, the highest degree in this case. After the 220th shifting, if the output from the output terminal 813 becomes .delta..sub.0, .alpha..sup.35 is the root of the error-location polynomial .delta. (z), which means an error occurs in the received word y.sub.35. In the same way, if the output from the output terminal 813 becomes .delta..sub.0 after the (220+i)th shifting, .alpha..sup.35-i is the root of the error-location polynomial .delta. (z), which means an error occurs in the received word y.sub.35-i.
As has been described, the conventional error-correcting encoder has to execute the encoding process symbol by symbol and a high-speed operation cannot be done.
The syndrome generating circuit of the conventional error-correcting decoder has to execute the syndrome generating process symbol by symbol and a high-speed operation cannot be done.
The Chien-Search circuit of the conventional error-correcting decoder has to execute the searching process symbol by symbol and a high-speed operation cannot be done.
Another conventional error-correcting decoder needs prior shifting according to the shortened length of the code in order to obtain the root of the error-location polynomial .delta. (z) of the shortened cyclic code on the GF, having code length n, by searching from the term of the highest degree by a Chien-Search. And the prior shifting takes a long time.